package com.example.demo.Calss18_dongtaiguihua;

import org.junit.Test;

/**
 * @program: java_base
 * @description: 压缩路径，动态规划
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/04 13:54
 */
public class Code01_MinPathSumDemo {

    /**
     * 方式一：基本动态规划，再创建一个 matrix[][] 数组，取值 右下角
     * 方式二：使用两个数组 ，轮换 行，
     * 方式三：使用一个数组，int[]
     */

    // 此为依赖左边 和 上边 左上角 可以是使用此方式，进行空间压缩
    // 使用 短 的 边 做数组进行遍历
    public static int minPathSum2(int[][] m) {
        if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
            return 0;
        }
        // 注意行列
        int col = m[0].length;
        int row = m.length;
        int[] arr = new int[col];

        arr[0] = m[0][0];
        // 第一行
        for (int i = 1; i < arr.length; i++) {
            arr[i] = arr[i - 1] + m[0][i];
        }
        // 遍历其他行
        // 先每一行 走一遍列
        for (int i = 1; i < row; i++) {
            arr[0] = m[i][0] + arr[0];
            for (int j = 1; j <col; j++) {
                arr[j] = Math.min(arr[j - 1], arr[j]) + m[i][j];
            }
        }
        return arr[col-1];
    }

    @Test
    public void test() {
        int[][] arr = {
                {1, 2},
                {1, 2},
                {1, 2},
                {3, 4}
        };

        System.out.println("arr[0].length 此 列数: " + arr[0].length);
        System.out.println("arr.length 行数:" + arr.length);
    }

}
